The present invention is directed towards a method and apparatus for interleaving and deinterleaving pseudorandomly a digital signal transmitted over a transmission channel which introduces random or burst errors or specific error patterns into the information to be transmitted. More particularly, the present invention is directed towards a method and apparatus utilizing pseudorandom convolutional interleaving to minimize the effect of these errors on the information being transmitted.
It is well known that errors in the transmission of digital information which would otherwise occur as a result of channel noise can be minimized by forward error-correction encoding an input digital sequence before it is applied to the transmission channel and then decoding the digital sequence when it is received at the other side of the transmission channel. This result follows from the Shannon channel coding theory which is described, for example, in A. J. Viterbi and J. K. Omura, Principles of Digital Communication and Coding (1979).
Most practical decoders are designed to correct random channel errors. The performance of random-error-correction decoders degrades in the face of burst errors in the transmission channel. If the error burst is too long, the decoder will not be able to properly reconstruct the original signal. An effective remedy to this problem is the use of an interleaver which randomizes the errors (separates them in time) and permits the decoder to work properly.
A known fixed convolutional interleaver-deinterleaver is illustrated in FIG. 1. Fixed convolutional interleaving has been described by J. S. Ramsey (reference: "Realization of Optimum Interleavers", IEEE Trans. on Inform. Th., Vol. IT-16, No. 3, pp. 338-345, May 1970) and G. D. Forney, Jr. (reference: "Burst-Correcting Codes for the Classical Bursty Channel", IEEE Trans. on Comm. Tech., Vol. COM-19, No. 5, pp. 772-781, Oct. 1971). As shown therein, an input signal (a continuous bit stream) is applied to an interleaver 10 which temporarily stores the received bits and transmits them in a different, but non-random, order from which they were received. In the embodiment illustrated, interleaver 10 comprises I delay lines 12-1 through 12-I, each of which receives a successive bit of the input digital signal. To this end, a commutator 14 switches from one delay line to the next in cyclic fashion at the bit rate of the input signal. While commutator 14 is shown as a mechanical element, it should be recognized by those skilled in the art that the commutator will normally be formed electronically using, for example, an appropriate transistor switching network.
Each of the delay lines, except delay line 12-1, includes a shift register (unnumbered) to which the bits applied to that delay line is stepped at a frequency of f/I, wherein f is the bit rate of the digital input signal. To this end, each time a given delay line 12-2 through 12-I receives another bit of the input digital signal, the shift register of that delay line will receive a clock signal which causes each of the elements stored in that shift register to shift to the right by 1. Each successive shift register has j more bits than the prior shift register such that each successive delay line delays the bits applied thereto by an additional j bits.
The output of each of the delay lines 12-1 through 12-I is connected to a transmission channel 16 via a commutator 18 which switches from one delay line to the next in cyclic fashion in synchronism with commutator 14. Again, while commutator 18 is shown as a mechanical commutator, an electronic commutator will normally be used.
As a result of the foregoing, an interleaver input of . . . a.sub.i a.sub.i+1 a.sub.i+2 . . . will result in the following interleaver output: ##EQU1## wherein I is the number of delay lines and J=jI.
The interleaved bits transmitted over the transmission channel 16 is received by a deinterleaver 20 which is constructed in the reverse manner to interleaver 10 such that the first delay line has (I-1)j bits of storage and the final delay line has no storage. The reconstructed input signal will appear at the output of deinterleaver 20 with a total delay of J(I-1) bits.
The result of the foregoing is that the convolutional interleaver of FIG. 1 (known generally as an (I,J) interleaver) will sufficiently randomize channel error bursts at the output of deinterleaver 20 as long as the error burst remains below J bits in length. Particularly, as long as the transmission channel 16 introduces error bursts of length no longer than J bits, then the errors in the output signal appearing at the output of deinterleaver 20 results from that burst will be separated by at least I-2 bits, which can be made acceptable by choosing the parameter I appropriately.
While the foregoing structure successfully randomizes error bursts below J bits in length, certain periodic error patterns (as opposed to error bursts) cannot be sufficiently randomized. For example, an error pattern having one error every J+1 bits would result in I successive bit errors at the output of deinterleaver 20. The primary object of the present invention is to provide protection against such periodic error patterns, as well as protection against error bursts of J bits or less.